package 力扣链表;

public class Leedcode148排序链表 {
    public ListNode sortList(ListNode head){
        return sortListHelper(head);
    }

    /**
     * 传入一个链表的头节点，我就能将链表的拍序
     * @param head
     * @return
     */
    private ListNode sortListHelper(ListNode head){
        //如果head为空或者只有一个节点，那么就直接返回他的节点
        if (head == null || head.next == null){
            return head;
        }
        //否则就至少存在两个节点,开始向下递归分解
        ListNode mid = middle(head);
        ListNode x = head;
        while (x != null && x.next != mid){
            x = x.next;
        }
        x.next = null;//断开前后链表
        //左右连边的链表怎么牌序我不知道，交给具有改功能的方法取实现。
        ListNode leftHead = sortListHelper(head);
        ListNode rightHead = sortListHelper(mid);
        //开始合并
        ListNode retHead = merge(leftHead,rightHead);
        return retHead;
    }

    private ListNode merge(ListNode leftHead, ListNode rightHead) {
        //创建一个辅助节点
        ListNode dummyHead = new ListNode(-1);
        ListNode tail = dummyHead;
        //左右节点都不为空，
        while (leftHead != null && rightHead != null){
            if (leftHead.val < rightHead.val){
                tail.next = leftHead;
                tail = leftHead;
                leftHead = leftHead.next;
            }else {
                tail.next = rightHead;
                tail = rightHead;
                rightHead = rightHead.next;
            }
        }
        //此时有一个节点的值为空
        if (leftHead != null){
            tail.next = leftHead;
        }
        if (rightHead != null){
            tail.next = rightHead;
        }
        return dummyHead.next;
    }

    /**
     * 找到链表的中间节点
     * @param head
     * @return
     */
    private ListNode middle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}
